package pri.zjy.backTracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhangjy
 * @description 全排列 II
 * @date 2025/6/14 0:32
 */
public class PermuteUnique_47 {

    public static void main(String[] args) {
        PermuteUnique_47 permuteUnique47 = new PermuteUnique_47();

//        int[] nums = {1, 1, 2};
//        int[] nums = {1, 2, 3};
        int[] nums = {3, 3, 0, 3};
//        permuteUnique47.permuteUnique(nums).forEach(System.out::println);
        permuteUnique47.permuteUnique3(nums).forEach(System.out::println);
    }

    /**
     * 个解
     * <p>
     * 分析：
     * <p>
     * 1.为什么要先排序？<br/>
     * ——因为去重时，是当前元素与前一位元素，在它俩元素值相同时进行去重；如果未经过排序，就无法达到去重的效果，如{1,2,1}。<br/>
     * <p>
     * 2.相同值的元素，如何对结果进行去重？<br/>
     * ——在【同一个树层上进行去重】；<br/>
     * 2.1.搜索过程（先横向遍历，再纵向遍历）+ 递归树可知，如{1,1,2}，其第一层横向遍历的递归树为：第一个元素-1-used[1,0,0]，第二个元素-1-used[0,1,1]；<br/>
     * 2.2.因为横向遍历是从前往后，那么对于前一个元素（即i-1），它的整个搜索过程，会得到所有目标结果；<br/>
     * 2.3.并且在nums有序的前提下，若nums[i-1]==nums[i]，那么当前元素（即i），完成整个搜索过程后，得到的所有目标排列与 i-1 结果一致；<br/>
     * 2.4.由上述搜索过程和递归树可知，当nums[i-1]==nums[i]，并且used[i-1]==0时，表明当前元素i得到的所有目标排列，与前一个元素i-1完全相同；所以，需要跳过处理当前元素，从而完成去重。
     * <p>
     * 3.在一个横向遍历中，如何跳过已经使用过的元素？<br/>
     * ——同一个横向遍历中，就是去重、记录元素、纵向递归等操作；此时相当于【树枝的去重】，操作同普通全排列；即used[i]==0（未使用时），才记录；否则跳过处理。
     */
    private List<List<Integer>> ans3 = new ArrayList<>();
    private List<Integer> path3 = new ArrayList<>();
    private int[] used3;

    public List<List<Integer>> permuteUnique3(int[] nums) {
        // nums元素可重复；每个元素只能用一次，找出所有目标排列
        // 重复元素如何去重？
        // ——在同一个树层下，当前元素与前一个元素的值相等时，并且前一个元素未使用过（used[i-1]==0），那么当前元素可跳过，从而完成去重。
        // 为什么同一个数层的值相同的前一个元素未使用过，才跳过当前元素，而不是前一个元素已经使用过？
        // 首先，搜索过程是，先横向遍历，再纵向遍历；如{1,1,2}，那么横向遍历中，前一个元素（第一个1）已经找过所有目标全排列，
        // 此时当前元素（第2个1）开始横向遍历，得到的目标全排列，必定与前一个的结果一致（因为它俩的元素值相同）；
        // 另外，前一个元素的used[0]一定为0，因为前面一轮横向遍历中会回溯。

        // 1.返回值void，入参：nums、used、path、ans，startIndex？
        // 不需要startIndex，因为全排列，每个元素都要从头判断并尝试记录，因为元素顺序不同，可能得到新的目标结果。
        // 2.递归终止条件
        // 找全排列，那么path.size()==nums.length时，表明找到一个全排列结果，则直接记录，并结束本层递归
        // 3.搜索过程
        // 3.1.先去重
        // 通过used，以及当前元素和前一个元素的值
        // 3.2.记录，元素值和使用情况
        // 当前元素已使用过，跳过
        // 未使用过，才记录
        // 3.3.向下递归
        // 每层递归的for循环都是从0开始，因为找的是排列结果，不是组合，那么元素顺序不同，就可能得到新的目标结果
        // 3.4.回溯

        if (nums.length == 0) return ans3;

        // 先升序排列
        Arrays.sort(nums);
        used3 = new int[nums.length];
        backtrack3(nums);
        return ans3;
    }

    public void backtrack3(int[] nums) {
        // 当path.size()==nums.length时，表明找到一个全排列结果，则直接记录并结束本层递归
        if (path3.size() == nums.length) {
            ans3.add(new ArrayList<>(path3));
            return;
        }

        // 横向遍历
        for (int i = 0; i < nums.length; i++) {
            // 当前元素与前一个元素的值相等，并且前一个元素未使用过；
            // 表明前一个元素已经完成其整个全排列过程，当前元素不用再次寻找，跳过当前元素
            if (i > 0 && nums[i] == nums[i - 1] && used3[i - 1] == 0)
                continue;

            // 当前元素使用过，直接跳过
            if (used3[i] == 1)
                continue;

            // 记录
            path3.add(nums[i]);
            used3[i] = 1;

            // 向下递归
            backtrack3(nums);

            // 回溯
            path3.remove(path3.size() - 1);
            used3[i] = 0;
        }
    }

    /**
     * 参考dmsxl
     */
    private List<List<Integer>> ans2 = new ArrayList<>();
    List<Integer> path2 = new ArrayList<>();
    // 0-未使用，1-已使用
    private int[] used2;
    public List<List<Integer>> permuteUnique2(int[] nums) {
        // 先升序排列
        Arrays.sort(nums);
        used2 = new int[nums.length];

        // 再递归回溯
        backtrack2(nums);

        return ans2;
    }

    public void backtrack2(int[] nums) {
        // 当path的元素 等于 nums[]长度，记录当前path，并结束本层递归
        if (path2.size() == nums.length) {
            ans2.add(new ArrayList<>(path2));
            return;
        }

        // 横向遍历
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == 1，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == 0，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used2[i - 1] == 0) continue;

            // 当前元素尚未使用过
            if (used2[i] == 0) {
                // 记录元素
                path2.add(nums[i]);
                used2[i] = 1;

                // 向下递归
                backtrack(nums);

                // 回溯
                path2.remove(path2.size() - 1);
                used2[i] = 0;
            }
        }
    }

    /**
     * 个解：错误！！！
     * <p>
     * 错误原因：记录元素时机不对
     */
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    // 0-未使用，1-已使用
    private int[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 可包含重复数字，所以在搜索过程中需要去重
        // 每个元素只能用一次

        // 回溯找到所有 不重复的全排列
        // 1.返回值和入参
        // 返回值void；
        // 入参：ans、path、nums[]、used[]、startIndex
        // used[]记录当前元素是否使用过，used[i]=0 表示未使用
        // startIndex固定为0，因为相同元素，但是顺序不同，也属于一种目标结果，所以每个元素都要判断。

        // 2.递归终止
        // 当path的元素 等于 nums[]长度，记录当前path，并结束本层递归

        // 3.搜索过程
        // for循环横向遍历
        // 3.1.搜索过程去重，若i>0 & nums[i] = nums[i-1] & used[i-1]==0，表明同一层的前一个元素已经使用过，则直接跳过
        // 3.2.记录元素
        // 3.3.向下递归
        // 3.4.回溯

        // 先升序排列
        Arrays.sort(nums);
        used = new int[nums.length];

        // 再递归回溯
        backtrack(nums);

        return ans;
    }

    public void backtrack(int[] nums) {
        // 当path的元素 等于 nums[]长度，记录当前path，并结束本层递归
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        // 横向遍历
        for (int i = 0; i < nums.length; i++) {
            // 搜索过程去重，若i>0 & nums[i] = nums[i-1] & used[i-1]==0，表明同一层的前一个元素已经使用过，则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;

            // 当前元素尚未使用过
            if (used[i] == 0) {
                // 记录元素
                path.add(nums[i]);
                used[i] = 1;

                // 向下递归
                backtrack(nums);

                // 回溯
                path.remove(path.size() - 1);
                used[i] = 0;
            }
        }
    }

}
